package nowcoder.backtrace;

/**
 * @author fance
 * @date 2018/5/7 13:46
 */
public class PrintBread {
    static int n = 5;
    static int sum = 0;
    static int[] path = new int[20];



    static void pop(int index) {
        sum -= path[index];
    }
    static void push(int index, int value) {
        path[index] = value;
        sum += value;
    }
    static void printPath(int k) {
        for (int i = 0; i < k; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println();
    }
    static void dfs(int k) {
        if (k > 19) {
            return;
        }
        if (sum == n) {
            printPath(k);
        } else if (sum < n) {
            for (int i = 1; i <= 3; i++) {
                push(k, i);
                dfs(k + 1);
                pop(k);
            }
        }
    }

    public static void main(String[] args) {

        dfs(0);
    }

}
